"""
3202. 找出有效子序列的最大长度 II
中等
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums 和一个 正 整数 k 。
nums 的一个 子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列 ：

(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k
返回 nums 的 最长有效子序列 的长度。


示例 1：

输入：nums = [1,2,3,4,5], k = 2

输出：5

解释：

最长有效子序列是 [1, 2, 3, 4, 5] 。

示例 2：

输入：nums = [1,4,2,3,1,4], k = 3

输出：4

解释：

最长有效子序列是 [1, 4, 1, 4] 。



提示：

2 <= nums.length <= 103
1 <= nums[i] <= 107
1 <= k <= 103
"""
from typing import List


class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        """
        创建二维数组f[x][y],x代表倒数第二个的%k的值，y代表倒数第一个%k的值
        假设遍历到当前结果为z时，代表要组成当前结尾为z，那么他可以从f[z][0]....f[z][k-1]中添加一个，f[z][0] = f[0][z] + 1 ,f[z][1] = f[1][z] + 1 ... f[z][k-1] = f[k-1][z] + 1
        """
        dp = [ [0] * k  for _ in range(k) ]
        for y in nums:  #此时结尾为y
            y = y % k
            #这遍历的是y在倒数第二位的情况，最终f[x][y] = f[y][x] + 1 ,这里遍历的就是f[y][x],其中x = [0,k)
            for x,time in enumerate(dp[y]):
                dp[x][y] = time + 1 #倒数第一位长度 = 倒数第二位长度 + 1
        return max(map(max,dp)) #map(max,dp)取每个维度最大值，代表倒数第二位所有情况的最大值数组，然后再取其中最大

    def maximumLength_Res1(self, nums: List[int], k: int) -> int:
        """
        创建二维数组f[x][y],x代表倒数第二个的%k的值，y代表倒数第一个%k的值
        假设遍历到当前结果为z时，代表要组成当前结尾为z，那么他可以从f[z][0]....f[z][k-1]中添加一个，f[z][0] = f[0][z] + 1 ,f[z][1] = f[1][z] + 1 ... f[z][k-1] = f[k-1][z] + 1
        :param nums:
        :param k:
        :return:
        """
        f = [[0] * k for _ in range(k)]
        for x in nums:
            x %= k
            for y, fxy in enumerate(f[x]):
                f[y][x] = fxy + 1
        return max(map(max, f))

if __name__ == '__main__':
    # print(Solution().maximumLength(nums = [1,2,3,4,5], k = 2))
    print(Solution().maximumLength(nums = [1,4,2,3,1,4], k = 3))